home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / READMEFiles / 2DLab.README < prev    next >
Text File  |  1992-08-29  |  8KB  |  155 lines

  1. README - 1/92 BR
  2.  
  3. 2DLab 3.0 is a modified version of 2DLab 2.0. In it, we (Mary, Bill and Renato) have added several algoritims that attempt to find a solution to the Travelling Salesperson  problem. We have also added a tour optimzer and changed the menus around. Version 3.0 is the result of a project for a graduate course in Mathematical Programming(CS720) in the Fall of 1991 at the University of Wisconsin-Madison. None of the functionality from version 2.0 has been changed. Below is the README text for version 2.0:
  4.  
  5.  
  6. README - 9/91 PJF
  7.  
  8. This directory contains sources for 2DLab, an interactive tool
  9. for visualizing some common geometric algorithms.
  10.  
  11. The source code for Voronoi diagrams and Delaunay tesselations
  12. was writen by Seth Teller (of SGI?) and available on many archive
  13. sites.
  14.  
  15. ** Ignore the warning messages that appear during compilation. ** 
  16.  
  17. ------------ Info from the Help Panel ----------------------------------
  18.  
  19. 2DLab animates a few algorithms from computational geometry and combinatorial optimization.  It was originally released in early 1990, back when I was a graduate student at Michigan State University.  In the process of updating the program for 2.0, things changed substantially, and many features were added.  I hope you like the program.
  20.  
  21. Running the program
  22. Two windows will appear when 2DLab is fired up.  The Geometry Window
  23. contains the data and the results of any algorithms run on the
  24. data.  The 2DLab Control window allows you to configure the data
  25. set, the algorithm, and the drawing that takes place.
  26.  
  27. When the program is invoked, the Drawing Window will contain ten
  28. points, and the selected algorithm (Prim's MST algorithm by default)
  29. will be applied to these points.  New points can be created by
  30. clicking in the window.  There is a `margin' around the border of
  31. the window  within which points will not be displayed, so If you
  32. click the mouse button and no point appears, you're probably too
  33. close to the edge (this margin was put in to make the Voronoi
  34. tesselation have a nice border.
  35.  
  36. A new set of random points (uniformly distributed within the window's
  37. usable region) can be generated by entering the desired number of
  38. points in the editable text field and pressing the Generate button.
  39.  
  40. The highlighted button in the RadioButton array in the Control
  41. Window identifies the particular algorithm to be `animated.'
  42.  
  43. The Anim/Disp button will run the appropriate animation when pressed.
  44. The Disp button will simply display the resulting data structure without
  45. animating.  It only works when the data structure has already been previously
  46. computed (i.e. ya gotta Anim before you can Disp).
  47. The Auto-Go checkbox specifies the program's behavior when new
  48. points are created with the mouse.  If the box is checked, the
  49. selected algorithm is run immediately when a new point is added.
  50.  
  51. The three color wells allow you to pick background, foreground,
  52. and highlighting colors.  When the display is drawn, points and
  53. line segments appear in the foreground color.  During animation,
  54. transient drawing is done using the highlight color.  By default,
  55. these colors are white, black, and  67% gray, respectively.  You
  56. can set them to anything you want using the standard color well
  57. tricks.
  58.  
  59. The line width slider controls how thickly everything is drawn (both
  60. points and lines).
  61.  
  62. The `Status' item displays informative (?) messages about the
  63. progress of the algorithm currently being animated, the drawing
  64. taking place, etc.
  65.  
  66. The Document menu allows you to save the current data set in a
  67. `generic' form, load a similarly-formatted file in for animation,
  68. and save the generated imagery as TIFF or EPS.  The file format
  69. for the data is simple.  The first number is the number of ordered
  70. pairs (%d), and the remaining numbers are the pairs (%f %f).  The error
  71. checking for I/O is pathetic, so please feed 2DLab well-behaved data files.
  72.  
  73. The Copy item of the Edit menu may be selected.  It sticks the contents of
  74. the Geometry window in the pasteboard.
  75.  
  76. Algorithms
  77. In the following brief descriptions, N is the number of 2D points,
  78. and the O-notation refers to time complexity rather than space
  79. complexity.  When the algorithms are invoked, those with quick eyes
  80. will notice some graphical razzle-dazzle as the data structure is
  81. constructed.  After the algorithm has completed, the `resulting'
  82. data structure will remain in the window.
  83.  
  84. - Prim's O(N^2) Minimal Spanning Tree (MST) algorithm.
  85.  
  86. - Kruskal's O(E log E) MST algorithm. WARNING: the implementation
  87. in this program is NOT optimal (it's actually O(N^2)).  Anybody
  88. who wants to hack together the priority queue stuff to implement
  89. the optimal algorithm is free to do so (lazy, that's me).
  90.  
  91. - Jarvis' O(N log N) convex hull construction algorithm.
  92.  
  93. - Graham's O(N log N) convex hull construction algorithm.
  94.  
  95. - Somebody's O(N log N) Voronoi diagram algorithm.
  96.  
  97. - Somebody's O(N log N) Delaunay triangulation algorithm.  (code
  98. for these last two algorithms was written by Seth Teller, who
  99. apparently used Fortune's netlib code as a basis).
  100.  
  101. - my own Gabriel Graph construction algorithm (it uses the
  102. Delaunay triangulation as a starting point).
  103.  
  104. - my own Relative Neighborhood Graph construction algorithm (again,
  105. using the Delaunay triangulation as a starting point).
  106.  
  107. Those interested in the details of the algorithms should refer to
  108. Preparata and Shamos' book on computational geometry.  Sedgewick's
  109. book also has covers geometric algorithms.  The GG and RNG haven't
  110. been used much, and are a little harder to find in the literature.
  111. Consult Toussaint, `The relative neighborhood graph of a finite
  112. point set', Pattern Recognition 12, 261-268 for info about the RNG.
  113. The Gabriel graph was used in Matula and Sokal, `Properties of
  114. Gabriel Graphs Relevant to Geographic Variation Research and the
  115. Clustering of Points in the Plane', Geographical Analysis 12,
  116. 205-222.   However, I don't have either of those papers in my
  117. posession.  This software was based on the discussion in Tuceryan
  118. and Chorzempa, `Relative Sensitivity of a family of closest-point
  119. graphs in computer vision applications', Pattern Recognition 24,
  120. 361-374.
  121.  
  122. Algorithms for 3.0:
  123. Stupid Neighbor: This is basically a test algorithm that connects point 0 to point 1, point 1 to point 2, and so on. It is useful for testing the tour optimizer, and seeing how bad an algorithm can be.(Bill Roth, 1991, previously unpublished)
  124. Cheapest Insertion: This algorithm finds the point that can be added with the least cost to the over all solution. (Salkin & Mathur, Foundations Of Integer Programming, 1989 North-Holland, p 683.)
  125. Nearest Neighbor: At a given point,  an arc will be drawn to the nearest unvisited point in the graph. (Lawler, Lenstra, et. al., The Traveling Salesman [sic] Problem, 1985, Wiley and Sons, p 150.)
  126. Nearest Addition: Given a set of connected points, the point nearest to an existing arc will be added to the graph.( Lawler, Lenstra, et. al., The Traveling Salesman [sic] Problem,1985, Wiley and Sons, p 157.)
  127. Farthest Insertion: This algorithm finds the point farthest away from all of the points in the tour, and finds the best place to insert it. (Lawler, Lenstra, et. al., The Traveling Salesman [sic] Problem,1985, Wiley and Sons, p 226.)
  128. The tour optimization procedure comes from Salkin & Mathur, Foundations Of Integer Programming, 1989 North-Holland, p 690-93.
  129.  
  130. About the authors.
  131. This program was written by:
  132.  
  133. Patrick Flynn
  134. Assistant Professor
  135. School of Electrical Engineering and Computer Science
  136. Washingon State University
  137. Pullman, WA 99164-2752
  138. (flynn@eecs.wsu.edu)
  139.  
  140. For Version 3.0:
  141. Mary Tork Roth "the Brains" (torkroth@cs.wisc.edu)
  142. Bill Roth        "the Brawn" (roth@cs.wisc.edu)
  143. Dr. Renato De Leone  "The Professor" (deleone@cs.wisc.edu)
  144. Computer Science Department
  145. University Of Wisconsin
  146. 1210 West Dayton Street
  147. Madison, WI 53706
  148.  
  149. If you find bugs, let us know.
  150. If you add functionality, let us know.
  151. If you like/hate it and just want to tell us, let us know.
  152. Date: 1/92.
  153.  
  154. Finis Coronat Opus.
  155.